Abstract:

With maturity of "the Internet of things" and establishment of cloud computing national standards, kinds of terminals appear quickly, and huge amounts of datas generation exponentially increase, so its crucial to construct index for the data. A fast Trie-tree index construction algorithm is proposed. All the strings are sorted and then the sorted strings are preprocessed, and after that a matrix with the element of triple is generated, consisting of the character, the horizontal and vertical offset of the character. The fast algorithm scans each column in turn and skips the repeated rows and columns with the same prefix according to offset value in triple array. The experimental results show that the fast algorithm significantly reduces the construction time compared with traditional algorithm and the performance is better than Aoes double-array Trie construction algorithm.

Key words: index construction, fast algorithm, Trie-tree, character frequency, double-array Trie